package Sort;

public class MergeSort {
    public static void main(String[] args) {
        int[] array = {34,43,65,6,7,23,23,6,467,764,345,563,8,987,698,34,234};
        sortSection(array);
        for (int i : array) {
            System.out.print(i + "  ");
        }
    }

    // 合并方法，其实就是双指针合并数组
    public static void merge(int[] array, int start1, int start2, int end){
        int len1 = start2 - start1;
        int[] temp = new int[len1];
        // 把左半部分copy进一个临时数组，原数组就变成了  _,_,_,_,_,_,x,x,x,x,x,x,x
        for (int i = 0; i < len1; i++) {
            temp[i] = array[start1 + i];
        }
//        System.arraycopy(array, start1, temp, 0, len1);
        // 双指针合并
        int p1 = 0, p2 = start2;
        for (int i = start1; i < end; ++i) {
            if (temp[p1] <= array[p2]) {
                array[i] = temp[p1];
                p1++;
                if (p1 == len1) { // 左半数组先遍历完，因为左右都是有序数组，因此可以直接break，剩下的右半数组就是有序的
                    break;
                }
            } else { // temp[p1] > array[p2]
                array[i] = array[p2];
                p2++;
                if (p2 > end) { // 右半边先遍历完，本来右半数组遍历完应该正好是end的，但是上一行p2++了，所以就是大于
                    // 接下来就是把左半数组剩下没有弄完的直接接到后面就可以了
                    while (p1 < len1) {
                        i++;    // 因为array[i]在当前的i已经被p2的最后一位赋值了，所以要手动往后移一位
                        array[i] = temp[p1];
                        p1++;
                    }
                }
            }
        }

    }

    // 递归拆分数组
    public static void sortSection(int[] array, int start, int end){
        // 终止条件
        if (start == end) {
            return;
        }
        int mid = (end - start) / 2 + start;
        // 左递归
        sortSection(array, start, mid);
        // 右递归
        sortSection(array, mid + 1, end);
        // 拆完之后要组装
        merge(array, start, mid + 1, end);
    }

    // wrap, 重载隐藏参数，Arrays.sort()就是这样写的
    public static void sortSection(int[] array) {
        sortSection(array, 0, array.length - 1);
    }
}
